import java.util.PriorityQueue;

class MedianFinder295 {
    private PriorityQueue<Integer> left ;
    private PriorityQueue<Integer> right ;
    private int len ; 
    public MedianFinder295() {
        this.left = new PriorityQueue<Integer>((o1,o2)->o2.compareTo(o1)) ;
        this.right = new PriorityQueue<>(); 
    }
    
    public void addNum(int num) {
        len ++ ;
        left.offer(num) ; 
        if(left.size() >= right.size()+2){
            right.offer(left.poll()) ; 
        }
       if(right.size() >= 1){
          if(left.peek() > right.peek()){
            int tmp = left.poll() ;
            left.offer(right.poll());
            right.offer(tmp) ; 
          }
       }
    }
    
    public double findMedian() {
        if(len %2 != 0){
            return left.peek() ;
        }
         
         return (left.peek()+right.peek())/2.0 ;
       }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */